package com.leetcode.search.backtracking;

/**
 * @author Dennis Li
 * @date 2020/7/27 11:30
 */
public class WordSearch_79 {

    private final int[][] directions = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    int width, high;

    String word;

    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        width = board[0].length;
        high = board.length;
        visited = new boolean[high][width];
        this.word = word;
        for (int i = 0; i < high; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (backtrack(board, i, j, 0)) return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, int i, int j, int step) {
        if (step == word.length() - 1 && board[i][j] == word.charAt(step)) return true;
        else if (board[i][j] != word.charAt(step)) return false;
        // 一定要记得退出策略
        // 表示来过此点
        visited[i][j] = true;
        for (int[] d : directions) {
            int x = j + d[1], y = i + d[0];
            if (x >= 0 && x < width && y >= 0 && y < high && !visited[y][x])
                // 当出现true时就返回，不然会进行大量的递归
                if (backtrack(board, y, x, step + 1)) return true;
        }
        // 这里进行回溯
        visited[i][j] = false;
        return false;
    }

}
